package com.jiang.专题.动态规划.Q516;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/28 19:07
 */
class Solution {
    public int longestPalindromeSubseq(String S) {
        // int len = S.length();
        // int[][] dp = new int[len][len];
        // for (int i = 0; i < len; i++) {
        //     dp[i][i] = 1;
        //     char c1 = S.charAt(i);
        //     for (int j = i - 1; j >= 0; j--) {
        //         char c2 = S.charAt(j);
        //         if (c1 == c2) {
        //             dp[j][i] = dp[j + 1][i - 1] + 2;
        //         } else {
        //             dp[j][i] = Math.max(dp[j][i - 1], dp[j + 1][i]);
        //         }
        //     }
        // }
        // return dp[0][len - 1];

        char[] s = S.toCharArray();
        int n = s.length;
        int[] f = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            f[i] = 1;
            int pre = 0; // 表示dp[i + 1][j - 1];
            for (int j = i + 1; j < n; j++) {
                int tmp = f[j];
                if (s[i] == s[j]) {
                    f[j] = pre + 2;
                } else {
                    f[j] = Math.max(f[j], f[j - 1]); // f[j]表示dp[i + 1][j]， f[j - 1]表示dp[i][j - 1]
                }
                pre = tmp;
            }
        }
        return f[n - 1];
    }
}
